package Datastruct.Algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序
 * 原理  将每个数的个位取出来进行 比较 然后比较十位 。。。一直比较到最大值的最高位 最后得出排序后结果
 *
 * 思想--讲所有的待比较数值统一设置为同样的数位长度，位数比较短的数前面补零，
 * 然后从最地位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列
 */
public class BasicSort {
    public static void main(String[] args) {

        int[] arrays = {53, 542, 3, 63, 14, 214, 154, 748, 616};

        System.out.println("原数组数据如下:" + Arrays.toString(arrays));

        arrays = sort(arrays);
        System.out.println("排序后的数组：" + Arrays.toString(arrays));
        //求出数组中最大的数
//        int max=arrays[0];
//        for(int i=1;i<arrays.length;i++){
//            if(arrays[i]>max){
//                max=arrays[i];
//            }
//        }
////        System.out.println(max);
//       int maxlen=(max+"").length();
//    //    System.out.println(maxlen);
//
//        /***
//         * 定义 十个桶来存储数据
//         * 还有一个辅助数组来统计每个桶中数据
//         */
//        int [][] bucket=new int[10][arrays.length];
//        int [] helper=new int[10];
//
//        for(int i=0;i< arrays.length;i++){
//            int localtion=arrays[i]/1%10;
//            bucket[localtion][helper[localtion]]=arrays[i];
//            helper[localtion]++;
//        }
//
//        /*
//        * 将第一次排序的结果放回原数组
//        * */
//        int index=0;
//        for(int i=0;i< helper.length;i++){
//            if(helper[i]!=0){
//                for(int j=0;j<helper[i];j++)
//                arrays[index++]=bucket[i][j];
//            }
//            helper[i]=0;        //数据取出后将数据清空
//        }
//
//        System.out.println("第一次排序结果："+Arrays.toString(arrays));
//
//        for(int i=0;i< arrays.length;i++){
//            int localtion=arrays[i]/10%10;
//            bucket[localtion][helper[localtion]]=arrays[i];
//            helper[localtion]++;
//        }
//
//        /*
//         * 将第二次排序的结果放回原数组
//         * */
//        int twoindex=0;
//        for(int i=0;i< helper.length;i++){
//            if(helper[i]!=0){
//                for(int j=0;j<helper[i];j++)
//                    arrays[twoindex++]=bucket[i][j];
//            }
//            helper[i]=0;   //取出数据后数组清空
//        }
//
//        System.out.println("第二次排序结果："+Arrays.toString(arrays));
//
//        for(int i=0;i< arrays.length;i++){
//            int localtion=arrays[i]/100%10;
//            bucket[localtion][helper[localtion]]=arrays[i];
//            helper[localtion]++;
//        }
//
//        /*
//         * 将第二次排序的结果放回原数组
//         * */
//        int threeindex=0;
//        for(int i=0;i< helper.length;i++){
//            if(helper[i]!=0){
//                for(int j=0;j<helper[i];j++)
//                    arrays[threeindex++]=bucket[i][j];
//            }
//            helper[i]=0;   //取出数据后数组清空
//        }
//
//        System.out.println("第二次排序结果："+Arrays.toString(arrays));
    }

    public static int[] sort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 查看最大位数
        int maxlenth = (max + "").length();

        /**
         * 定义一个二维数组 当做十个来计数
         * 定义一个辅助数组来统计每个桶子的个数
         */

        int[][] buket = new int[10][arr.length];
        int[] helper = new int[10];

        /*
         * 根据最大位的数是多少进行多少次排序
         * */
        for (int i = 0, n = 1; i < maxlenth; i++, n = n * 10) {
            for (int j = 0; j < arr.length; j++) {
                int location = arr[j] / n % 10;
                buket[location][helper[location]] = arr[j];
                helper[location]++;
            }
            int index = 0;
            for (int k = 0; k < helper.length; k++) {
                if (helper[k]!= 0) {
                    for (int m = 0; m < helper[k]; m++) {
                        arr[index++] = buket[k][m];
                    }
                }
                helper[k]=0;  //数据取出后清零
            }
        }
        return arr;
    }
}

